package com.zm.demo.core.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author zoum
 * @create 2020/1/15 10:53
 */
public class FindFrequentTreeSum {

    int max = 0;
    List<Integer> rList = new ArrayList<>();
    public int[] findFrequentTreeSum(TreeNode root) {

        Map<Integer, Integer> calcResult = new HashMap<>();
        findFrequentTreeSum(root, calcResult);
        int[] result = new int[rList.size()];
        for (int i = 0; i < rList.size(); i++) {
            result[i] = rList.get(i);
        }
       return result;
    }

    public int findFrequentTreeSum(TreeNode node, Map<Integer, Integer> result) {
        if (node == null){
            return 0;
        }else {
            int sum = node.val;
            if (node.left != null){
                sum += findFrequentTreeSum(node.left, result);
            }
            if (node.right != null){
                sum += findFrequentTreeSum(node.right, result);
            }
            result.compute(sum, (k,v)-> v== null ? 1 : v+1);
            if (max < result.get(sum)){
                max = result.get(sum);
                rList.clear();
                rList.add(sum);
            }else if (max == result.get(sum)){
                rList.add(sum);
            }
            return sum;
        }
    }
}
